package offer.zixing.chapter06;

import java.util.Stack;

/**
 * 矩阵中最大的矩形
 *
 * 请在一个由0、1组成的矩阵中找出最大的只包含1的矩形并输出它的面积。
 * 例如在图6.6的矩阵中，最大的只包含1的矩阵如阴影部分所示，它的面积是6。
 */
public class Test040 {
    private static char[][] metaMatrix = {{1, 0, 1, 0, 0}, {0, 0, 1, 1, 1}, {1, 1, 1, 1, 1}, {1, 0, 0, 1, 0}};

    public static void main(String[] args) {
        System.out.println(maximalRectangle(metaMatrix));
    }

    public static int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int[] heights = new int[matrix[0].length];
        int maxArea = 0;
        for (char[] row : matrix) {
            for (int i = 0; i < row.length; i++) {
                if (row[i] == '0') {
                    heights[i] = 0;
                } else {
                    heights[i]++;
                }
            }
            maxArea = Math.max(maxArea, largestRectangleArea(heights));
        }
        return maxArea;
    }

    private static int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int maxArea = 0;
        for (int i = 0; i < heights.length; i++) {
            while (stack.peek() != -1 && heights[stack.peek()] >= heights[i]) {
                int height = heights[stack.pop()];
                int width = i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        while ((stack.peek() != -1)) {
            int height = heights[stack.pop()];
            int width = heights.length - stack.peek();
            maxArea = Math.max(maxArea, height * width);
        }
        return maxArea;
    }
}
